0283. 移动零【简单】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 双指针（1）
• 3. 🎯 s.2 - 双指针（2）

1. 📝 题目描述

• leetcode

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

请注意，必须在不复制数组的情况下原地对数组进行操作。

---

示例 1：

输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]

---

示例 2：

输入: nums = [0]
输出: [0]

---

提示:

• 1 <= nums.length <= 10^4
• -2^31 <= nums[i] <= 2^31 - 1

---

进阶：你能尽量减少完成的操作次数吗？

2. 🎯 s.1 - 双指针（1）

1.js

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var moveZeroes = function (nums) {
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] !== 0) continue
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[j] === 0) continue
      ;[nums[i], nums[j]] = [nums[j], nums[i]]
      break
    }
  }
}

• 时间复杂度：$O(n^2)$，最坏情况下每个零都需要遍历后续所有元素
• 空间复杂度：$O(1)$，只使用了常数级别的额外空间

算法思路：i 指向 0 的时候，j 指针就开始向前探路，找找 i 后边儿第一个不是 0 的成员跟 i 交换。

3. 🎯 s.2 - 双指针（2）

1.js

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var moveZeroes = function (nums) {
  let slow = 0 // 指向下一个非零元素应该放置的位置

  // 将所有非零元素移到数组前面
  for (let fast = 0; fast < nums.length; fast++) {
    if (nums[fast] !== 0) {
      nums[slow] = nums[fast]
      slow++
    }
  }

  // 将剩余位置填充0
  for (let i = slow; i < nums.length; i++) {
    nums[i] = 0
  }
}

• 时间复杂度：$O(n)$，遍历数组两次
• 空间复杂度：$O(1)$，原地修改数组

算法思路：

• 使用双指针，slow 指向下一个非零元素应该放置的位置
• fast 遍历整个数组，遇到非零元素就放到 slow 位置，然后 slow++
• 第一次遍历后，所有非零元素已按原顺序移到数组前面
• 第二次遍历将 slow 之后的位置全部填充为 0